﻿//二叉树的基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	int height;					//平衡因子
	ElemType data;			//数据元素
	struct node* lchild;	//指向左孩子节点
	struct node* rchild;	//指向右孩子节点
} BTNode;
void CreateBTree(BTNode*& b, const char* str)	//创建二叉树
{
	BTNode* St[MaxSize], * p = NULL;
	int top = -1, k, j = 0;
	char ch;
	b = NULL;				//建立的二叉树初始时为空
	ch = str[j];
	while (ch != '\0')  	//str未扫描完时循环
	{
		switch (ch)
		{
		case '(':top++; St[top] = p; k = 1; break;		//为左孩子节点
		case ')':top--; break;
		case ',':k = 2; break;                      		//为孩子节点右节点
		default:p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (b == NULL)                    	 	//*p为二叉树的根节点
				b = p;
			else  								//已建立二叉树根节点
			{
				switch (k)
				{
				case 1:St[top]->lchild = p; break;
				case 2:St[top]->rchild = p; break;
				}
			}
		}
		j++;
		ch = str[j];
	}
}
void DestroyBTree(BTNode*& b)
{
	if (b != NULL)
	{
		DestroyBTree(b->lchild);
		DestroyBTree(b->rchild);
		free(b);
	}
}
BTNode* FindNode(BTNode* b, ElemType x)
{
	BTNode* p;
	if (b == NULL)
		return NULL;
	else if (b->data == x)
		return b;
	else
	{
		p = FindNode(b->lchild, x);
		if (p != NULL)
			return p;
		else
			return FindNode(b->rchild, x);
	}
}
BTNode* LchildNode(BTNode* p)
{
	return p->lchild;
}
BTNode* RchildNode(BTNode* p)
{
	return p->rchild;
}
int BTHeight(BTNode* b)
{
	int lchildh, rchildh;
	if (b == NULL) return(0); 				//空树的高度为0
	else
	{
		if (b->lchild != NULL)
			b->lchild->height = lchildh = BTHeight(b->lchild);	//求左子树的高度为lchildh
		else
			lchildh = 0;
		if (b->rchild != NULL)
			b->rchild->height = rchildh = BTHeight(b->rchild);	//求右子树的高度为rchildh
		else
			rchildh = 0;
		return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
	}
}
void DispBTree(BTNode* b)
{
	if (b != NULL)
	{
		printf("%c", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild != NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}

bool is_binsorttree(BTNode* b) {
	/*if (t == 0)
		return ;*/
	if (b->lchild)
		if (b->lchild->data <= b->data && is_binsorttree(b->lchild))
			//return 1
			;
		else {
			//t = 0;
			//printf("该数不是二叉排序树！！");
			return 0;
		}
	if (b->rchild)
		if (b->rchild->data > b->data && is_binsorttree(b->rchild))
			//return 1
			;
		else {
			//t = 0;
			//printf("该不是二叉排序树！！");
			return 0;
		}
	return 1;
}

int abs(int a, int b) {
	if ((a - b) > 0 || (a - b) == 0)
		return a - b;
	return b - a;

}

bool is_avl(BTNode* b) {
	int x, y;
	if (b == NULL)
		return 1;
	if (!is_avl(b->lchild) || !is_avl(b->rchild))
		return 0;
	//is_avl(b->rchild);
	b->lchild == NULL ? x = 0 : x = b->lchild->height;
	b->rchild == NULL ? y = 0 : y = b->rchild->height;
	int t = abs(x, y);
	if (t < 1 || t == 1)
		return 1;
	else
		return 0;

}

//以下主函数用做调试
void main()
{
	BTNode* b[3];
	CreateBTree(b[0], "5(4(2(,3),),7(6,8))");
	CreateBTree(b[1], "5(2(1,4(3,)),6(,7))");
	CreateBTree(b[2], "5(4(2(,3),),7(8,6))");
	for (int i = 0; i < 3; i++) {
		DispBTree(b[i]);
		b[i]->height = BTHeight(b[i]);
		printf("\n");

		if (is_binsorttree(b[i]))
			if (is_avl(b[i]))
				printf("该树是平衡二叉排序树！！\n");
			else
				printf("该树是二叉排序树，但是不平衡！！\n");
		else
			printf("该树不是二叉排序树！！\n");
	}
}
